#include <stdlib.h>
#include <stdio.h>

typedef struct Trie
{
	struct Trie* children[26];
	int isEnd;
} Trie;

Trie* trieCreate()
{
	Trie* node = (Trie*)malloc(sizeof(Trie));
	if (node == NULL) exit(EXIT_FAILURE);
	else
	{
		for (int i = 0; i < 26; i++)
			node->children[i] = NULL;
		node->isEnd = 0;
		return node;
	}
}

void trieInsert(Trie* obj, char* word)
{
	int ch;
	while (*word) // 判断*word是否等于'\0'
	{
		ch = *word - 'a';
		if (obj->children[ch] == NULL)
			obj->children[ch] = trieCreate();
		obj = obj->children[ch];
		word++;
	}
	obj->isEnd++;
}

int trieSearch(Trie* obj, char* word)
{
	int ch;
	while (*word) // 判断*word是否等于'\0'
	{
		ch = *word - 'a';
		if (obj->children[ch] == NULL)
			return 0;
		obj = obj->children[ch];
		word++;
	}
	return obj->isEnd;
}

int trieStartsWith(Trie* obj, char* prefix)
{
	int ch;
	while (*prefix) // 判断*prefix是否等于'\0'
	{
		ch = *prefix - 'a';
		if (obj->children[ch] == NULL)
			return 0;
		obj = obj->children[ch];
		prefix++;
	}
	return 1;
}

void trieFree(Trie* obj)
{
	if (obj == NULL) return;
	int i;
	for (i = 0; i < 26; i++)
		trieFree(obj->children[i]);
	free(obj);
}